- Ordenación Shell Sort
- El Shell Sort es un ordenamiento de disminución incremental, nombrado así debido a su inventor Donald Shell. Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento. Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando inserción directa), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K. En algún momento el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado. Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1. "Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos." Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa. El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.
pre
Procedimiento Shell Sort;
/pre
Ejemplo: Para el arreglo a = [6, 1, 5, 2, 3, 4, 0] Tenemos el siguiente recorrido:
pre
Recorrido Salto Lista Ordenada Intercambio
1 3 2,1,4,0,3,5,6 (6,2), (5,4), (6,0)
2 3 0,1,4,2,3,5,6 (2,0)
3 3 0,1,4,2,3,5,6 Ninguno
4 1 0,1,2,3,4,5,6 (4,2), (4,3)
5 1 0,1,2,3,4,5,6 Ninguno
/pre
Enciclopedia Universal. 2012.
